/**
 * 生成一个随机array，使用二分查找在array中查找一个随机数
 * C语言二分查找的库函数为bsearch()
 * 二分查找存在两种情况，找的到和找不到
 * 找的到时判断自定义二分查找函数和库函数地址是否一致
 * 找不到时判断二者返回值，是否都未找到
 **/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

int binary_search(int num[], int len, int item)
{
    int low = 0;
    int high = len-1, mid, guess;
    while(low <= high){
        mid = (low+high) / 2;
        guess = num[mid];
        if(guess == item) return mid;
        else if(guess > item) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

static int
cmpintp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

bool test_binary_search(int num[], int len)
{
    
    srand((unsigned)time(NULL));
    for (int i = 0; i < len; i++){
        num[i] = rand() % 100;
    }
    qsort(num, len, sizeof(int),cmpintp);
    int item = rand() % 100;
    int position = binary_search(num, len, item);
    int *address= (int *)bsearch(&item, num, len, sizeof(int), cmpintp);
    if(position >= 0){
        // 存在这个数，二者指向相同的地址
        return &num[position] == address;
    } else {
        // 不存在这个数
        return address == NULL && position == -1;
    }
    return false;
}
int main()
{
    int len = 30;
    int num[len];
    int count = 1 << 10;
    bool result;
    for(int i=0; i< count; i++){
        result = test_binary_search(num, len);
        if (result == false) {
            printf("failure\n");
            return -1;
        }
    }
    printf("sucess\n");
    return 0;
}